package com.mikelouis.test.scala.coursera

/**
 * Created by yuazhu on 5/14/2015.
 */
object Sort {
  def insertionSort[T: Ordering](listToSort: List[T])(implicit ord: Ordering[T]): List[T] = {
    def isort(xs: List[T]): List[T] = xs match {
      case Nil => Nil
      case y :: ys => insert(y, isort(ys))
    }

    def insert(x: T, xs: List[T]): List[T] = xs match {
      case Nil => List(x)
      case y :: ys => if (ord.compare(x, y) <= 0) x :: xs else y :: insert(x, ys)
    }

    isort(listToSort)
  }

  def quickSort(ls: List[Int]): List[Int] = ls match {
    case Nil => Nil
    case base :: tail =>
      val (left, rigth) = tail.partition(_ < base)
      quickSort(left) ::: base :: quickSort(rigth)
  }

  def msort(xs: List[Int]): List[Int] = {
    val n = xs.length / 2
    if (n == 0) xs
    else {
      def merge(xs: List[Int], ys: List[Int]): List[Int] = xs match {
        case Nil => ys
        case x :: x1 =>
          ys match {
            case Nil => xs
            case y :: ys1 =>
              if (x < y) x :: merge(x1, ys)
              else y :: merge(xs, ys1)
          }
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst), msort(snd))
    }
  }

  def main(args: Array[String]) {
    println(insertionSort(List(2, 5, 3, 8)))
    println(insertionSort(List(2, 1, 4, 6, 2, 9, 66, 54, 78, 91, 20, 47, 0, 4, -23)))

    println(quickSort(List(4, 3, 5, 2, 20, 1)))

    println(msort(List(4, 3, 5, 2, 20, 1)))
  }

}
